home *** CD-ROM | disk | FTP | other *** search
/ Whiteline: Alpha / Whiteline Alpha.iso / linux / atari / source / source.lzh / atari-linux-0.01pl3 / fs / ext2 / dcache.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-06-05  |  7.1 KB  |  338 lines
  1. /*
  2.  *  linux/fs/ext2/dcache.c
  3.  *
  4.  *  Copyright (C) 1992, 1993  Remy Card (card@masi.ibp.fr)
  5.  *
  6.  */
  7.  
  8. /*
  9.  * dcache.c contains the code that handles the directory cache used by
  10.  * lookup() and readdir()
  11.  */
  12.  
  13. #include <asm/segment.h>
  14.  
  15. #include <linux/fs.h>
  16. #include <linux/ext2_fs.h>
  17. #include <linux/kernel.h>
  18. #include <linux/string.h>
  19.  
  20. #ifndef DONT_USE_DCACHE
  21.  
  22. #define DCACHE_NAME_LEN    32
  23.  
  24. struct dir_cache_entry {
  25.     unsigned short dev;
  26.     unsigned long dir;
  27.     unsigned long ino;
  28.     char name[DCACHE_NAME_LEN + 1];
  29.     int len;
  30.     struct dir_cache_entry * queue_prev;
  31.     struct dir_cache_entry * queue_next;
  32.     struct dir_cache_entry * prev;
  33.     struct dir_cache_entry * next;
  34. };
  35.  
  36. static struct dir_cache_entry * first = NULL;
  37. static struct dir_cache_entry * last = NULL;
  38. static struct dir_cache_entry * first_free = NULL;
  39. static int cache_initialized = 0;
  40. #ifdef EXT2FS_DEBUG_CACHE
  41. static int hits = 0;
  42. static int misses = 0;
  43. #endif
  44.  
  45. #define CACHE_SIZE 128
  46.  
  47. static struct dir_cache_entry dcache[CACHE_SIZE];
  48.  
  49. #define HASH_QUEUES 16
  50.  
  51. static struct dir_cache_entry * queue_head[HASH_QUEUES];
  52. static struct dir_cache_entry * queue_tail[HASH_QUEUES];
  53.  
  54. #define hash(dev,dir)    ((dev ^ dir) % HASH_QUEUES)
  55.  
  56. /*
  57.  * Initialize the cache
  58.  */
  59. static void init_cache (void)
  60. {
  61.     int i;
  62.  
  63.     dcache[0].prev = NULL;
  64.     dcache[0].next = &dcache[1];
  65.     dcache[0].queue_next = dcache[0].queue_prev = NULL;
  66.     for (i = 1; i < CACHE_SIZE - 1; i++) {
  67.         dcache[i].prev = &dcache[i - 1];
  68.         dcache[i].next = &dcache[i + 1];
  69.         dcache[i].queue_next = dcache[i].queue_prev = NULL;
  70.     }
  71.     dcache[i].prev = &dcache[i - 1];
  72.     dcache[i].next = NULL;
  73.     dcache[i].queue_next = dcache[i].queue_prev = NULL;
  74.     first_free = &dcache[0];
  75.     for (i = 0; i < HASH_QUEUES; i++)
  76.         queue_tail[i] = queue_head[i] = NULL;
  77.     cache_initialized = 1;
  78. }
  79.  
  80. /*
  81.  * Find a name in the cache
  82.  */
  83. static struct dir_cache_entry * find_name (int queue, unsigned short dev,
  84.                        unsigned long dir,
  85.                        const char * name, int len)
  86. {
  87.     struct dir_cache_entry * p;
  88.  
  89.     for (p = queue_head[queue]; p != NULL && (p->dev != dev ||
  90.          p->dir != dir || p->len != len ||
  91.          strncmp (name, p->name, p->len) != 0);
  92.          p = p->queue_next)
  93.         ;
  94.     return p;
  95. }
  96.  
  97. #ifdef EXT2FS_DEBUG_CACHE
  98. /*
  99.  * List the cache entries for debugging
  100.  */
  101. static void show_cache (const char * func_name)
  102. {
  103.     struct dir_cache_entry * p;
  104.  
  105.     printk ("%s: cache status\n", func_name);
  106.     for (p = first; p != NULL; p = p->next)
  107.         printk ("dev:%04x, dir=%4lu, name=%s\n",
  108.             p->dev, p->dir, p->name);
  109. }
  110. #endif
  111.  
  112. /*
  113.  * Add an entry at the beginning of the cache
  114.  */
  115. static void add_to_cache (struct dir_cache_entry * p)
  116. {
  117.     p->prev = NULL;
  118.     p->next = first;
  119.     if (first)
  120.         first->prev = p;
  121.     if (!last)
  122.         last = p;
  123.     first = p;
  124. }
  125.  
  126. /*
  127.  * Add an entry at the beginning of a queue
  128.  */
  129. static void add_to_queue (int queue, struct dir_cache_entry * p)
  130. {
  131.     p->queue_prev = NULL;
  132.     p->queue_next = queue_head[queue];
  133.     if (queue_head[queue])
  134.         queue_head[queue]->queue_prev = p;
  135.     if (!queue_tail[queue])
  136.         queue_tail[queue] = p;
  137.     queue_head[queue] = p;
  138. }
  139.  
  140. /*
  141.  * Remove an entry from the cache
  142.  */
  143. static void remove_from_cache (struct dir_cache_entry * p)
  144. {
  145.     if (p->prev)
  146.         p->prev->next = p->next;
  147.     else
  148.         first = p->next;
  149.     if (p->next)
  150.         p->next->prev = p->prev;
  151.     else
  152.         last = p->prev;
  153.     p->prev = NULL;
  154.     p->next = NULL;
  155. }
  156.  
  157. /*
  158.  * Remove an entry from a queue
  159.  */
  160. static void remove_from_queue (int queue, struct dir_cache_entry * p)
  161. {
  162.     if (p->queue_prev)
  163.         p->queue_prev->queue_next = p->queue_next;
  164.     else
  165.         queue_head[queue] = p->queue_next;
  166.     if (p->queue_next)
  167.         p->queue_next->queue_prev = p->queue_prev;
  168.     else
  169.         queue_tail[queue] = p->queue_prev;
  170.     p->queue_prev = NULL;
  171.     p->queue_next = NULL;
  172. }
  173.  
  174. /*
  175.  * Invalidate all cache entries on a device (called by put_super() when
  176.  * a file system is unmounted)
  177.  */
  178. void ext2_dcache_invalidate (unsigned short dev)
  179. {
  180.     struct dir_cache_entry * p;
  181.     struct dir_cache_entry * p2;
  182.  
  183.     if (!cache_initialized)
  184.         init_cache ();
  185.     for (p = first; p != NULL; p = p2) {
  186.         p2 = p->next;
  187.         if (p->dev == dev) {
  188.             remove_from_cache (p);
  189.             remove_from_queue (hash (p->dev, p->dir), p);
  190.             p->next = first_free;
  191.             first_free = p;
  192.         }
  193.     }
  194. #ifdef EXT2FS_DEBUG_CACHE
  195.     show_cache ("dcache_invalidate");
  196. #endif
  197. }
  198.  
  199. /*
  200.  * Lookup a directory entry in the cache
  201.  */
  202. unsigned long ext2_dcache_lookup (unsigned short dev, unsigned long dir,
  203.                   const char * name, int len)
  204. {
  205.     char our_name[EXT2_NAME_LEN];
  206.     int queue;
  207.     struct dir_cache_entry * p;
  208.  
  209.     if (!cache_initialized)
  210.         init_cache ();
  211.     if (len > DCACHE_NAME_LEN)
  212.         return 0;
  213.     memcpy (our_name, (char *) name, len);
  214.     our_name[len] = '\0';
  215. #ifdef EXT2FS_DEBUG_CACHE
  216.     printk ("dcache_lookup (%04x, %lu, %s, %d)\n", dev, dir, our_name, len);
  217. #endif
  218.     queue = hash (dev, dir);
  219.     if ((p = find_name (queue, dev, dir, our_name, len))) {
  220.         if (p != first) {
  221.             remove_from_cache (p);
  222.             add_to_cache (p);
  223.         }
  224.         if (p != queue_head[queue]) {
  225.             remove_from_queue (queue, p);
  226.             add_to_queue (queue, p);
  227.         }
  228. #ifdef EXT2FS_DEBUG_CACHE
  229.         hits++;
  230.         printk ("dcache_lookup: %s,hit,inode=%lu,hits=%d,misses=%d\n",
  231.             our_name, p->ino, hits, misses);
  232.         show_cache ("dcache_lookup");
  233. #endif
  234.         return p->ino;
  235.     } else {
  236. #ifdef EXT2FS_DEBUG_CACHE
  237.         misses++;
  238.         printk ("dcache_lookup: %s,miss,hits=%d,misses=%d\n",
  239.             our_name, hits, misses);
  240.         show_cache ("dcache_lookup");
  241. #endif
  242.         return 0;
  243.     }
  244. }
  245.  
  246. /*
  247.  * Add a directory entry to the cache
  248.  *
  249.  * This function is called by ext2_lookup(), ext2_readdir()
  250.  * and the functions which create directory entries
  251.  */
  252. void ext2_dcache_add (unsigned short dev, unsigned long dir, const char * name,
  253.               int len, unsigned long ino)
  254. {
  255.     struct dir_cache_entry * p;
  256.     int queue;
  257.  
  258.     if (!cache_initialized)
  259.         init_cache ();
  260. #ifdef EXT2FS_DEBUG_CACHE
  261.     printk ("dcache_add (%04x, %lu, %s, %d, %lu)\n",
  262.         dev, dir, name, len, ino);
  263. #endif
  264.     if (len > DCACHE_NAME_LEN)
  265.         return;
  266.     queue = hash (dev, dir);
  267.     if ((p = find_name (queue, dev, dir, name, len))) {
  268.         p->dir = dir;
  269.         p->ino = ino;
  270.         if (p != first) {
  271.             remove_from_cache (p);
  272.             add_to_cache (p);
  273.         }
  274.         if (p != queue_head[queue]) {
  275.             remove_from_queue (queue, p);
  276.             add_to_queue (queue, p);
  277.         }
  278.     } else {
  279.         if (first_free) {
  280.             p = first_free;
  281.             first_free = p->next;
  282.         } else {
  283.             if (!last)
  284.                 panic ("dcache_add: last == NULL\n");
  285.             else {
  286.                 p = last;
  287.                 last = p->prev;
  288.                 if (last)
  289.                     last->next = NULL;
  290.                 remove_from_queue (hash (p->dev, p->dir), p);
  291.             }
  292.         }
  293.         p->dev = dev;
  294.         p->dir = dir;
  295.         p->ino = ino;
  296.         strncpy (p->name, name, len);
  297.         p->len = len;
  298.         p->name[len] = '\0';
  299.         add_to_cache (p);
  300.         add_to_queue (queue, p);
  301.     }
  302. #ifdef EXT2FS_DEBUG_CACHE
  303.     show_cache ("dcache_add");
  304. #endif
  305. }
  306.  
  307. /*
  308.  * Remove a directory from the cache
  309.  *
  310.  * This function is called by the functions which remove directory entries
  311.  */
  312. void ext2_dcache_remove (unsigned short dev, unsigned long dir,
  313.              const char * name, int len)
  314. {
  315.     struct dir_cache_entry * p;
  316.     int queue;
  317.  
  318.     if (!cache_initialized)
  319.         init_cache ();
  320. #ifdef EXT2FS_DEBUG_CACHE
  321.     printk ("dcache_remove (%04x, %lu, %s, %d)\n", dev, dir, name, len);
  322. #endif
  323.     if (len > DCACHE_NAME_LEN)
  324.         return;
  325.     queue = hash (dev, dir);
  326.     if ((p = find_name (queue, dev, dir, name, len))) {
  327.         remove_from_cache (p);
  328.         remove_from_queue (queue, p);
  329.         p->next = first_free;
  330.         first_free = p;
  331.     }
  332. #ifdef EXT2FS_DEBUG_CACHE
  333.     show_cache ("dcache_remove");
  334. #endif
  335. }
  336.  
  337. #endif
  338.